/**
 * @a https://leetcode.cn/problems/smallest-k-lcci/
 */

#include "common.h"
class Solution
{
public:
    vector<int> smallestK(vector<int> &arr, int k)
    {
        q_select(arr.begin(), arr.end(), k);
        return {arr.begin(), arr.begin() + k};
    }
    void q_select(vector<int>::iterator begin, vector<int>::iterator end,
                  int k)
    {

        if (k == 0 || begin == end)
            return;
        if (end - begin == 1)
            return;
        int pivot_index = rand() % (end - begin);
        int pivot = *(begin + pivot_index);
        auto left = begin, right = end - 1, curr = begin;
        while (curr <= right)
        {
            if (pivot > *curr)
            {
                iter_swap(curr++, left++);
            }
            else if (pivot < *curr)
            {
                iter_swap(curr, right--);
            }
            else
            {
                ++curr;
            }
        }
        int len_left = left - begin;
        int len_pivot = right - left + 1;
        int len_right = end - right - 1;
        if (k < len_left)
            return q_select(begin, left, k);
        else if (k <= len_left + len_pivot)
        {
            return;
        }
        else
        {
            return q_select(right + 1, end, k - len_left - len_pivot);
        }
    }
};